package Algorithm.sort.basic;

import utils.CommonUtils;

import java.util.Arrays;

/**
 * 算法思想：将要排序的n个元素初始化为一个大（小）根堆，逐次从堆中提取堆顶元素，每次提取后将堆底元素放到堆顶，再重构剩下的元素为大（小）根堆，提取出的序列即为有序序列。
 *
 * 大（小）根堆即为树中每个节点都大于等于（小于等于）其子节点的完全二叉树 （概念不清楚可参考: 文章）
 *
 * 完全二叉树的性质：将 下标从0开始 长度为n 的数组视为一棵完全二叉树，则下标 n/2 -1 的元素为树的最后一个分支节点，节点i若存在左孩子，则其下标为2i+1，若存在右孩子，则其下标为2i+2
 *
 * 性能：初始化大根堆时间复杂度为O(n)，之后每次调整大根堆只需要将堆顶元素向下“冒泡”，时间复杂度为O(logn)，共需调整n次。故时间复杂度平均O(nlogn)，最好O(nlogn)，最坏O(nlogn) 参考证明。空间复杂度O(1)。不稳定
 *
 * 适用场景：Top-K问题
 */
public class HeapSort {

    public static void main(String[] args) {
//        int[] A = new int[]{4,6,3,5,9,2,1,2,4,5,6};
//        heapSort(A);
//        System.out.println(Arrays.toString(A));

        int[] A = CommonUtils.getRandomNums(100, 1000);
        int[] B = Arrays.copyOf(A,A.length);
        long time = System.currentTimeMillis();

        ShellSort.shellSort2(A);
        long time1 = System.currentTimeMillis();
        System.out.println("方法一耗时"+(time1-time));

        int[] max = getMaxNums(B, 10);
        long time2 = System.currentTimeMillis();
        System.out.println("方法二耗时"+(time2-time1));
    }


//----------------------------------------------------------------------------------------------------------------------
    //todo 是否可以继续优化 将堆顶设置在数组末尾 这样就避免了多次交换
    /**
     * 对数组A进行堆排序
     */
    static void heapSort(int[] A) {
        int length = A.length;
        buildMaxHeap(A, length);
        while (length > 1) {
            //将堆顶元素即堆的最大值与最后一个元素交换，然后将新的堆顶元素向下“冒泡”将剩余元素调整为大根堆
            CommonUtils.swap(A, 0, length-1);
            maxHeadAdjust(A, 0, --length);
        }
    }

    /**
     * 构建大根堆：
     * ①首先将长为length的数组视作一棵完全二叉树
     * ②从最后一个分支结点（下标为n/2 - 1 向下取整）开始检查，如果以该元素为根的子树是大根堆，则不操作，进行下一步，否则将此子树调整为大根堆
     * ③继续逐个检查下标为i-1,i-2等分支结点为根的子树，进行第二步的判断和调整，直到检查到根节点i=0为止
     */
    static void buildMaxHeap(int[] A, int length) {
        for (int i = length/2 - 1;i >= 0;i--) {
            maxHeadAdjust(A, i, length);
        }
    }

    //此时i节点的子树必定已为调整好的堆，故只需将i节点往下“冒泡”，直到找到一个合适的位置
    static void maxHeadAdjust(int[] A, int i, int length) {
        int temp = A[i];
        //A[2*i+1]即为A[i]的左孩子
        for (int j = 2*i+1;j < length;j=2*i+1) {
            //取当前结点的孩子结点中较大的结点
            if (j+1 < length && A[j] < A[j+1]) {
                j++;
            }
            //如果当前节点小于较大孩子节点，则交换。否则temp已到达合适位置 退出循环
            if (temp < A[j]) {
                A[i] = A[j];
                i=j;
            } else {
                break;
            }
        }
        A[i] = temp;
    }

//----------------------------------------------------------------------------------------------------------------------

    /**
     * 使用堆排序得出nums数组的前n个最大值
     */
    static int[] getMaxNums(int[] nums, int n) {
        int heapLength = Math.min(nums.length, n);
        int[] heapNums = Arrays.copyOf(nums, heapLength);
        buildMinHeap(heapNums, heapLength);
        for (int i=heapLength;i < nums.length;i++) {
            if (nums[i] > heapNums[0]) {
                heapNums[0] = nums[i];
                minHeadAdjust(heapNums, 0, heapLength);
            }
        }
        return heapNums;
    }

    /**
     * 构建最小堆
     */
    static void buildMinHeap(int[] A, int length) {
        for (int i = length/2 - 1;i >= 0;i--) {
            minHeadAdjust(A, i, length);
        }
    }

    //此时i节点的子树必定已为调整好的堆，故只需将i节点往下“冒泡”，直到找到一个合适的位置
    static void minHeadAdjust(int[] A, int i, int length) {
        int temp = A[i];
        //A[2*i+1]即为A[i]的左孩子
        for (int j = 2*i+1;j < length;j=2*i+1) {
            //取当前结点的孩子结点中较小的结点
            if (j+1 < length && A[j] > A[j+1]) {
                j++;
            }
            //如果大于较小孩子节点，则交换。否则temp已到达合适位置 退出循环
            if (temp > A[j]) {
                A[i] = A[j];
                i=j;
            } else {
                break;
            }
        }
        A[i] = temp;
    }
}
/**
 * 简评：堆排序适用于记录数较多的场景，例如从一亿个记录中选取100个最大值，首先使用一个大小为100的数组，读入前100个数建立小根堆，
 * 然后依次读入剩下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整根堆，待数据全部读取完毕，堆中100个数即为所求
 */